{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Shortest and Lexicographically Smallest Beautiful String"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #sliding-window"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #滑动窗口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: shortestBeautifulSubstring"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最短且字典序最小的美丽子字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个二进制字符串 <code>s</code> 和一个正整数 <code>k</code> 。</p>\n",
    "\n",
    "<p>如果 <code>s</code> 的某个子字符串中 <code>1</code> 的个数恰好等于 <code>k</code> ，则称这个子字符串是一个 <strong>美丽子字符串</strong> 。</p>\n",
    "\n",
    "<p>令 <code>len</code> 等于 <strong>最短</strong> 美丽子字符串的长度。</p>\n",
    "\n",
    "<p>返回长度等于 <code>len</code> 且字典序 <strong>最小</strong> 的美丽子字符串。如果 <code>s</code> 中不含美丽子字符串，则返回一个 <strong>空</strong> 字符串。</p>\n",
    "\n",
    "<p>对于相同长度的两个字符串 <code>a</code> 和 <code>b</code> ，如果在 <code>a</code> 和 <code>b</code> 出现不同的第一个位置上，<code>a</code> 中该位置上的字符严格大于 <code>b</code> 中的对应字符，则认为字符串 <code>a</code> 字典序 <strong>大于</strong> 字符串 <code>b</code> 。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，<code>\"abcd\"</code> 的字典序大于 <code>\"abcc\"</code> ，因为两个字符串出现不同的第一个位置对应第四个字符，而 <code>d</code> 大于 <code>c</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"100011001\", k = 3\n",
    "<strong>输出：</strong>\"11001\"\n",
    "<strong>解释：</strong>示例中共有 7 个美丽子字符串：\n",
    "1. 子字符串 \"<em><strong>100011</strong></em>001\" 。\n",
    "2. 子字符串 \"<strong><em>1000110</em></strong>01\" 。\n",
    "3. 子字符串 \"<strong><em>100011001</em></strong>\" 。\n",
    "4. 子字符串 \"1<strong><em>00011001</em></strong>\" 。\n",
    "5. 子字符串 \"10<strong><em>0011001</em></strong>\" 。\n",
    "6. 子字符串 \"100<em><strong>011001</strong></em>\" 。\n",
    "7. 子字符串 \"1000<strong><em>11001</em></strong>\" 。\n",
    "最短美丽子字符串的长度是 5 。\n",
    "长度为 5 且字典序最小的美丽子字符串是子字符串 \"11001\" 。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"1011\", k = 2\n",
    "<strong>输出：</strong>\"11\"\n",
    "<strong>解释：</strong>示例中共有 3 个美丽子字符串：\n",
    "1. 子字符串 \"<em><strong>101</strong></em>1\" 。\n",
    "2. 子字符串 \"1<em><strong>011</strong></em>\" 。\n",
    "3. 子字符串 \"10<em><strong>11</strong></em>\" 。\n",
    "最短美丽子字符串的长度是 2 。\n",
    "长度为 2 且字典序最小的美丽子字符串是子字符串 \"11\" 。 \n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"000\", k = 1\n",
    "<strong>输出：</strong>\"\"\n",
    "<strong>解释：</strong>示例中不存在美丽子字符串。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 100</code></li>\n",
    "\t<li><code>1 &lt;= k &lt;= s.length</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [shortest-and-lexicographically-smallest-beautiful-string](https://leetcode.cn/problems/shortest-and-lexicographically-smallest-beautiful-string/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [shortest-and-lexicographically-smallest-beautiful-string](https://leetcode.cn/problems/shortest-and-lexicographically-smallest-beautiful-string/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"100011001\"\\n3', '\"1011\"\\n2', '\"000\"\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestBeautifulSubstring(self, s: str, k: int) -> str:\n",
    "        # buffer = list()\n",
    "        # curr_len = 101\n",
    "        # curr_idx = -1\n",
    "        # for i in range(len(s)):\n",
    "        #     if s[i] == \"1\":\n",
    "        #         buffer.append(i)\n",
    "        #     if len(buffer)<k:\n",
    "        #         continue\n",
    "        #     else:\n",
    "        #         len_tmp = buffer[-1]-buffer[-k]+1\n",
    "        #         if curr_len> len_tmp:\n",
    "        #             curr_len = len_tmp\n",
    "        #             curr_idx = len(buffer)-k\n",
    "        #         elif curr_len == len_tmp:\n",
    "        #             # compare lexical\n",
    "        #             for j in range(1, k):\n",
    "        #                 if buffer[curr_idx+j]>buffer[-k+j]:\n",
    "        #                     curr_idx = len(buffer)-k\n",
    "        # if curr_len == 101:\n",
    "        #     return \"\"\n",
    "        # return s[buffer[curr_idx]:buffer[curr_idx+k]]\n",
    "        buffer = list()\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == \"1\":\n",
    "                buffer.append(i)\n",
    "        if len(buffer)<k:\n",
    "            return \"\"\n",
    "        curr_len = 102\n",
    "        \n",
    "        for i in range(k-1, len(buffer)):\n",
    "            if curr_len>buffer[i]-buffer[i-k+1]+1:\n",
    "                curr_len = buffer[i]-buffer[i-k+1]+1\n",
    "                curr_idx = i\n",
    "            elif curr_len == buffer[i]-buffer[i-k+1]+1:\n",
    "                # compare the lexical order\n",
    "                if s[buffer[curr_idx-k+1]:buffer[curr_idx]+1]>s[buffer[i-k+1]:buffer[i]+1]:\n",
    "                    curr_idx = i\n",
    "                # for m in range(1, k):\n",
    "                #     if buffer[curr_idx-k+1+m]==buffer[i-k+1+m]:\n",
    "                #         continue\n",
    "                #     elif buffer[curr_idx-k+1+m]>buffer[i-k+1+m]:\n",
    "                #         curr_idx = i\n",
    "                #         break\n",
    "                #     else:\n",
    "                #         break\n",
    "        return s[buffer[curr_idx-k+1]:buffer[curr_idx]+1]\n",
    "            \n",
    "                            \n",
    "                    \n",
    "                \n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestBeautifulSubstring(self, s: str, k: int) -> str:\n",
    "        # 1的个数小于k\n",
    "        if s.count('1') < k:\n",
    "            return ''\n",
    "            \n",
    "        for size in count(k):  # 从 k 开始枚举\n",
    "            ans = ''\n",
    "            for i in range(size, len(s) + 1):\n",
    "                t = s[i - size: i]\n",
    "                if (ans == '' or t < ans) and t.count('1') == k:\n",
    "                    ans = t\n",
    "            if ans: return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestBeautifulSubstring(self, s: str, k: int) -> str:\n",
    "        # 思路：队列记录元素为“1”的下标，队列里保持k个元素，遍历一次\n",
    "        shortestLen = len(s) + 1\n",
    "        shortestSub = \"\"\n",
    "        queue = []\n",
    "        for i, x in enumerate(s):\n",
    "            if x == '1':\n",
    "                queue.append(i)\n",
    "                if len(queue) == k:\n",
    "                    sub = s[queue[0]:queue[-1] + 1]\n",
    "                    if len(sub) == k:   # 特殊情况，直接返回\n",
    "                        return sub\n",
    "                    if len(sub) < shortestLen:\n",
    "                        shortestLen = len(sub)\n",
    "                        shortestSub = sub\n",
    "                    elif len(sub) == shortestLen and sub < shortestSub:\n",
    "                        shortestSub = sub\n",
    "                    queue = queue[1:]\n",
    "        return shortestSub\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestBeautifulSubstring(self, s: str, k: int) -> str:\n",
    "\n",
    "        if s.count('1')<k:return ''\n",
    "        n = len(s)\n",
    "        mp = defaultdict(int)\n",
    "        \n",
    "        left = 0\n",
    "        ans = s\n",
    "\n",
    "        for right in range(n):\n",
    "            mp[s[right]]+=1\n",
    "            while mp['1'] == k:\n",
    "                t = s[left:right+1]\n",
    "                if len(t)<len(ans) or len(t) == len(ans) and t< ans:\n",
    "                    ans = t\n",
    "                mp[s[left]] -=1\n",
    "                left += 1\n",
    "        return ans\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
